package xyz.scootaloo.oj.offer

import org.junit.Test
import xyz.scootaloo.console.app.support.Tester

/**
 * @author flutterdash@qq.com
 * @since 2021/4/11 12:11
 */
class P33 {

    private fun verifyPostorder(postorder: IntArray): Boolean {
        if (postorder.size <= 1) return true
        return verifyPostorderCore(postorder, 0, postorder.size - 1)
    }

    private fun verifyPostorderCore(postorder: IntArray, left: Int, right: Int): Boolean {
        if (left >= right) // 子树只有一个节点, 或者没有节点
            return true
        val pivot = check(postorder, left, right)
        if (pivot == -1) return false
        return verifyPostorderCore(postorder, left, pivot - 1) &&
                verifyPostorderCore(postorder, pivot, right - 1)
    }

    private fun check(postorder: IntArray, left: Int, right: Int): Int {
        val rootValue = postorder[right]
        // 查找右子树的区间
        var pivot = left
        for (idx in (right - 1) downTo left) {
            if (postorder[idx] < rootValue) {
                pivot = idx
                break
            }
        }
        for (idx in (pivot - 1) downTo left) {
            if (postorder[idx] > rootValue)
                return -1
        }
        return pivot
    }

    @Test
    fun test0() {
        Tester.createTest(this::verifyPostorder)
            .addCase(intArrayOf(1, 6, 3, 2, 5), false)
            .addCase(intArrayOf(1, 3, 2, 6, 5), true)
            .addCase(intArrayOf(5, 4, 3, 2, 1), true)
            .testAndShow()
    }

}
